# 使用递归和分而治之的思想解决问题

# 快速排序，平均情况O(nlogn)[调用深度logn，每层涉及O(n)个元素]，最差情况O(n^2)
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        less = [i for i in arr[1:] if i <= pivot]
        greater = [i for i in arr[1:] if i > pivot]
        return quick_sort(less) + [pivot] + quick_sort(greater)


# 传统的通过交换数据的方式实现快速排序
def quick_sort_swap(arr, low, high):
    if low < high:
        pivot = arr[low]
        i = low
        j = high
        while i <= j:
            if arr[i] <= pivot:
                i += 1
                continue
            if arr[j] >= pivot:
                j -= 1
                continue
            else:
                temp = arr[i]
                arr[i] = arr[j]
                arr[j] = temp
                i += 1
                j -= 1
        arr[low] = arr[j]
        arr[j] = pivot
        quick_sort_swap(arr, low, j - 1)
        quick_sort_swap(arr, j + 1, high)


# 通过划分和不断交换的方式实现快排
def partition(arr, low, high):
    pivot = arr[low]
    while low < high:
        while low < high and arr[high] >= pivot:
            high -= 1
        arr[low] = arr[high]
        while low < high and arr[low] <= pivot:
            low += 1
        arr[high] = arr[low]
    arr[low] = pivot
    return low


def quick_sort_partition(arr, low, high):
    if low < high:
        pivot = partition(arr, low, high)
        quick_sort_partition(arr, low, pivot - 1)
        quick_sort_partition(arr, pivot + 1, high)
